;; Non-robust Monotone Chain algorithm for computing the convex hull of a set of 2D points.
;; Copyright (C) 2021  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.compgeom.convex-hull.monotone-chain
  (:require [mazama.compgeom.core :refer [point-orient2d]]))

;;;; NOTE
;;;;
;;;; 1. This software may fail if floating point values are used.
;;;;
;;;; 2. This software assumes that:
;;;;    the x-axis increases to the right;
;;;;    the y-axis increases DOWNWARD.

(defn- half-hull
  "Add point `c` to the `hull`, discarding previous points on the hull if necessary."
  [include-all-points-on-boundary hull c]
  (loop [hull hull
         c c]
    (if (< (count hull) 2)
      (conj hull c)
      (let [hull- (pop hull)
            b (peek hull)
            a (peek hull-)]
        (case (point-orient2d a b c)
          -1 (recur hull- c)
          0 (if include-all-points-on-boundary
              (conj hull c)
              (recur hull- c))
          1 (conj hull c))))))

(defn convex-hull
  "Compute the convex hull of the 2D points in `S`.
  https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain"
  ([S]
   (convex-hull S false))
  ([S include-all-points-on-boundary]
   (if (< (count S) 3)
     S
     (let [P (sort S)
           f (partial half-hull include-all-points-on-boundary)
           U (reduce f [] P)]
       ; If every point is on the first half-hull then we are done
       (if (== (count U) (count P))
         U
         (let [L (reduce f [] (reverse P))]
           (concat (pop U) (pop L))))))))
